package graph;

import java.util.Arrays;

/**
 * 基于邻接矩阵的有权无向图
 */
public class WeightedMGraph {
    /**
     * 顶点数
     */
    private final int V;
    /**
     * 边数
     */
    private int E;
    /**
     * 邻接矩阵
     */
    private int[][] matrix;

    /**
     * 构造函数
     * 
     * @param V 顶点数
     */
    public WeightedMGraph(int V) {
        this.V = V;
        this.matrix = new int[V][V];
        for (int i = 0; i < this.V; i++) {
            for (int j = 0; j < this.V; j++) {
                if (i == j) {
                    this.matrix[i][j] = 0;
                } else {
                    this.matrix[i][j] = Integer.MAX_VALUE / 2;
                }
            }
        }
    }

    /**
     * 增加边，连接v和w
     * 
     * @param v
     * @param w
     */
    public void addEdge(int v, int w, int weight) {
        if (validateV(v) && validateV(w)) {
            matrix[v - 1][w - 1] = weight;
            matrix[w - 1][v - 1] = weight;
            E++;
        }
    }

    /**
     * 获取顶点数
     */
    public int V() {
        return V;
    }

    /**
     * 获取边数
     * 
     * @return
     */
    public int E() {
        return E;
    }

    @Override
    public String toString() {
        return Arrays.deepToString(matrix);
    }

    /**
     * 获取v的所有邻接点
     * 
     * @param v
     * @return v的所有邻节点
     */
    public int[] adj(int v) {
        if (validateV(v)) {
            int[] returnValue = new int[V];
            int j = 0;
            for (int i = 0; i < matrix[v - 1].length; i++) {
                if (matrix[v - 1][i] > 0) {
                    returnValue[j] = i + 1;
                    j++;
                }
            }
            int[] copyOfReturnValue = new int[j];
            for (int i = 0; i < copyOfReturnValue.length; i++) {
                copyOfReturnValue[i] = returnValue[i];
            }
            return copyOfReturnValue;
        } else {
            return null;
        }

    }

    /**
     * 获取节点v的度
     * 
     * @param v
     * @return
     */
    public int getDegree(int v) {
        if (validateV(v)) {
            return adj(v).length;
        } else {
            return 0;
        }
    }

    public boolean validateV(int v) {
        if (v < 1 || v > V) {
            System.out.println("请输入在1到" + V + "之间的顶点");
            return false;
        } else {
            return true;
        }
    }

    /**
     * 多源最短路径算法
     * 
     * @return 最短路径矩阵
     */
    public int[][] multiSourceShortestPath() {
        return floyd();
    }

    public int[][] floyd() {
        int[][] D = new int[this.V][this.V];
        for (int i = 0; i < this.V; i++) {
            for (int j = 0; j < this.V; j++) {
                D[i][j] = matrix[i][j];
            }
        }

        for (int k = 0; k < this.V; k++) {
            for (int i = 0; i < this.V; i++) {
                for (int j = 0; j < this.V; j++) {
                    if (D[i][k] + D[k][j] < D[i][j]) {
                        D[i][j] = D[i][k] + D[k][j];
                    }
                }
            }
        }

        return D;
    }

    /**
     * Minimum Scanning Tree 最小生成树
     * Tree: V个顶点有V-1条边，无回路
     * Scanning: 包含全部顶点，V-1条边全部都在顶点里
     * Minimun：边的权重和最小
     * @return 最小生成树索引
     */
    public int[] MST() {
        return prim();
    }

    /**
     * Prim算法适用于稠密图, 时间复杂度为V^2
     * @return
     */
    public int[] prim(){
        // 记录最小权重
        int[] lowcost = new int[this.V];
        // 记录距离最短的点
        int[] closest = new int[this.V];

        // 初始化
        for (int i = 0; i < lowcost.length; i++) {
            lowcost[i] = matrix[i][0];
            closest[i] = 1;
        }

        // 找到剩余的v-1个点
        for (int i = 1; i < this.V ; i++){
            int min = Integer.MAX_VALUE / 2;
            int k = 0;
            // 找到距离最短的点
            for (int j = 1; j < lowcost.length; j++){
                if (lowcost[j] != 0 && lowcost[j] < min){
                    min = lowcost[j];
                    k = j;
                }
            }
            // 如果找不到，就退出
            if (k == 0){
                System.out.println("最小生成树不存在！");
                return null;
            }
            // 如果找到了，开始更新距离
            lowcost[k] = 0;
            for (int l = 1; l < lowcost.length; l++){
                if (lowcost[l] != 0 && matrix[l][k] < lowcost[l]){
                    lowcost[l] = matrix[l][k];
                    closest[l] = k + 1;
                }
            }
        }

        return closest;

    }
}